/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-01-14
 * Time: 11:27
 */
// 1、无头单向非循环链表实现
public class MyLinkedList {
    public class listNode{
        int data;
        listNode next;
    }
    public listNode head;
    //创建一个链表用于测试
    public void createList(){
        listNode node1=new listNode();
        listNode node2=new listNode();
        listNode node3=new listNode();
        listNode node4=new listNode();

        node1.data=1;
        node2.data=2;
        node3.data=3;
        node4.data=4;

        head=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
    }
    //头插法
    public void addFirst(int data){
        listNode node=new listNode();
        node.data=data;
        node.next=head;
        head=node;
    }
    //尾插法
    public void addLast(int data){
        if(head==null){
            return;
        }
        listNode cur=head;
        listNode node=new listNode();
        node.data=data;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
    //任意位置插入,第一个数据节点为0号下标,index是下标
    public boolean addIndex(int index,int data){
        if(index<0||index>size()){
            return false;
        }
        listNode cur=head;
        int count=0;
        listNode node=new listNode();
        node.data=data;
        //头插
        if(index==0){
            node.next=head;
            head=node;
            return true;
        }
        //尾插
        if(index==size()){
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
            return true;
        }
        //中间插,需要找到这个下标的前一个位置index-1的位置
        cur=head;
        for(int i=0;i<index-1;i++){
            cur=cur.next;
        }
        listNode curnext=cur.next;
        node.next=curnext;
        cur.next=node;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(head==null){
            return false;
        }
        listNode cur=head;
        while(cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        listNode cur=head;
        //我们要判断这个链表是否为空
        if(head==null){
            return;
        }
        //接下来我们需要判断一下这个链表的头结点是不是要删除的结点
        if(head.data==key){
            head=head.next;
            return;
        }
        //我们要去遍历这个链表找到要删除结点的前一个结点的位置
        //然后进行删除操作
        while(cur.next!=null){
            if(cur.next.data==key){
                listNode node=cur.next;//这个就是要删除的结点
                cur.next=node.next;
                break;
            }
            cur=cur.next;
        }

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        listNode cur=head;
        //我们要判断这个链表是否为空
        if(head==null){
            return;
        }
        //我们要去遍历这个链表找到要删除的结点
        //然后进行删除操作
        listNode prevnode=head;
        listNode curnode=head.next;
        while(curnode!=null){
            if(curnode.data==key){
                prevnode.next=curnode.next;
                curnode=curnode.next;
            }else{
                prevnode=curnode;
                curnode=curnode.next;
            }
        }
        //接下来去判断头结点是否需要删除
        if(head.data==key){
            head=head.next;
        }
    }
    //得到单链表的长度
    public int size(){
        listNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //打印
    public void display(){
        listNode cur=head;
        while(cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //清空
    public void clear(){
        head=null;
    }
}
